package leetcode.day_2021_05_25_2021_05_31;

import leetcode.day_2020_12_14_12_21.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 98. 验证二叉搜索树
 * https://leetcode-cn.com/problems/validate-binary-search-tree/
 */
public class LeetCode0098 {
    public static void main(String[] args) {
        System.out.println(2147483647 - (-2147483648));
    }

    // 中序遍历非递归法
    public boolean isValidBST(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        dfs(root, list);
        for(int i=1; i<list.size(); i++) {
            if (list.get(i) <= list.get(i-1)) {
                return false;
            }
        }
        return true;
    }

    public void dfs(TreeNode root, List<Integer> list) {
        if(root == null) {
            return;
        }
        if (root.left != null) {
            dfs(root.left, list);
        }
        list.add(root.val);
        if (root.right != null) {
            dfs(root.right, list);
        }
    }

    // 中序遍历递归法1
    public boolean isValidBST2(TreeNode root) {
        long min = Long.MIN_VALUE;
        long max = Long.MAX_VALUE;
        return dfs2(root, min, max);
    }

    public boolean dfs2(TreeNode root, long min, long max) {
        if (root == null) {
            return true;
        }
        long val = root.val;
        return val>min && val<max && dfs2(root.left, min, val) && dfs2(root.right, val, max);
    }

    // 中序遍历递归法2
    long pre = Long.MIN_VALUE;
    public boolean isValidBST3(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST3(root.left)) {
            return false;
        }
        if (root.val <= pre) {
            return false;
        }
        long pre = root.val;
        return isValidBST3(root.right);
    }
}
